package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

public class _8_Solution {

    @Test
    public void test(){
        int[][] matrix = {
                { 5,-4,-3, 4},
                {-3,-4, 4, 5},
                { 5, 1, 5,-4}};
        int k = 8;
        //0
        System.out.println(maxSumSubmatrix(matrix,k));
    }

    public int maxSumSubmatrix(int[][] matrix, int k) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            int[] sum = new int[matrix[i].length];
            for (int m = i; m < matrix.length; m++) {
                for (int n = 0; n < matrix[m].length; n++) {
                    sum[n] += matrix[m][n];
                }
                for (int p = 0; p < sum.length; p++) {
                    int temp = sum[p];
                    if (temp == k) {
                        return k;
                    }
                    if (temp > max && temp < k) {
                        max = temp;
                    }
                    for (int q = p+1; q < sum.length; q++) {
                        temp += sum[q];
                        if (temp == k) {
                            return k;
                        }
                        if (temp > max && temp < k) {
                            max = temp;
                        }
                    }
                }
            }
        }
        return max;
    }
}
